public class MaxPathSum {
    private int res = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        getMaxPathSumOnNodeAsABranch(root);
        return res;
    }

    public int getMaxPathSumOnNodeAsABranch(TreeNode root) {
        if (root == null) return 0;
        int leftPathSum = Math.max(getMaxPathSumOnNodeAsABranch(root.left),0);
        int rightPathSum = Math.max(getMaxPathSumOnNodeAsABranch(root.right),0);
        int sum = leftPathSum + rightPathSum + root.val;
        res = Math.max(res, sum);
        return Math.max(leftPathSum,rightPathSum)+root.val;
    }
}
